package Tree;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 106.从中序与后序遍历序列构造二叉树
 * 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
 */
public class buildTree {
    /**
     * 一刷
     */
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length == 0 || postorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postorder.length - 1]);

        Map<Integer, Integer> inordermap = new HashMap<>();

        for (int i = 0; i < inorder.length; i++) {
            inordermap.put(inorder[i], i);
        }

        int index = inordermap.get(postorder[postorder.length - 1]);
        int leftinorder[] = Arrays.copyOfRange(inorder, 0, index);
        int rightinorder[] = Arrays.copyOfRange(inorder, index + 1, inorder.length);

        int leftpostorder[] = Arrays.copyOfRange(postorder, 0, leftinorder.length);
        int rightpostorder[] = Arrays.copyOfRange(postorder, leftinorder.length, postorder.length - 1);
        root.left = buildTree(leftinorder, leftpostorder);
        root.right = buildTree(rightinorder, rightpostorder);

        return root;
    }

    public static void main(String[] args) {
        int[] inorder = new int[]{9, 3, 15, 20, 7};
        int[] postorder = new int[]{9, 15, 7, 20, 3};
        buildTree tree = new buildTree();
        tree.buildTree(inorder, postorder);
    }
}
